<?php


class Solution
{
    /**
     * @param String $s
     * @return String
     */
    function removeDuplicateLetters($s) {
        $res = '';
        $counts = []; //用于排序，当  count[s[i]]=1 表示s[i]字符之后还有一个相同的字符
        $tmp = []; //统计出现次数， 当 tmp[s[i]] =0 表示栈中没有s[i]单元
        $stack=new SplStack;
        for($i=0;$i<strlen($s);$i++){
            if( isset($counts[$s[$i]]) ){
                $counts[$s[$i]]++;
            }else{
                $counts[$s[$i]]=1;
            }
            $tmp[ $s[$i] ] =0;
        }
        for($i=0;$i<strlen($s);$i++){
            $counts[$s[$i]]--; //表明该字符已经被使用
            // push前进行判断
            if(  $tmp[$s[$i]] >0 ) continue;
            while( !$stack->isEmpty() && $stack->top()>$s[$i]  ){
                //因为要保证递减的前提是要保证字符序，所以当后面没有该字符时不再出栈
                if( $counts[$stack->top()] ==0  ) break;
                $tmp[ $stack->pop() ] --;
            }
            $stack->push( $s[$i] );
            $tmp[$s[$i]] =1;
        }
        while(!$stack->isEmpty()) $res = $stack->pop().$res;
        return $res;
    }


}